#ifndef MYGRAPH_H_INCLUDED
#define MYGRAPH_H_INCLUDED

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

class EdgeNode{ // 边节点类
private:
    int dest; // 边的终点下标（从0开始）
    EdgeNode* link; // 指向下一个边节点

public:
    EdgeNode();
    EdgeNode(int dest, EdgeNode* link);
    ~EdgeNode();
    int getDest();
    EdgeNode* getNext();
    void setDest(int dest);
    void setNext(EdgeNode* link);
};

class VertexNode{ // 顶点节点类
private:
    char data; // 顶点节点值
    EdgeNode* firstEdge; // 边节点链表表头

public:
    VertexNode();
    VertexNode(char data, EdgeNode* firstEdge);
    ~VertexNode();
    char getData();
    EdgeNode* getFirstEdge();
    void setData(char data);
    void setFirstEdge(EdgeNode* firstEdge);
};

class MyGraph{ // 图类
private:
    int nodeNum; // 顶点数目
    int edgeNum; // 边数目
    VertexNode* VexList; // 邻接表

public:
    MyGraph();
    MyGraph(int nodeNum, int edgeNum, char* nodeList, int* edgeStartList, int* edgeEndList);
    ~MyGraph();
    int getNodeNum();
    int getEdgeNum();
    string printGraph(); // 打印图

    // 辅助函数
    void DFS(int v, int* visited, string& result);
    void BFS(int v, int* visited, string& result);
    int getFirstNeighbor(int v, int* visited);
    int getNextNeighbor(int v, int w, int* visited);

    // DFS、BFS函数
    string graph_BFS_Traverse();
    string graph_DFS_Traverse();
};



#endif // MYGRAPH_H_INCLUDED
